home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 2 / LSD and 17bit Compendium Deluxe - Volume II.iso / a / prog / cprog / pointinpoly.lha / PointInPoly.txt
Encoding:
Text File  |  1993-03-06  |  1.2 KB  |  59 lines
  1. From pdxgate!usenet.ee.pdx.edu!reed!henson!news.u.washington.edu!usenet.coe.montana.edu!caen!uunet!mcsun!sun4nl!bsoatr!bskewe!kewe Tue Mar  2 15:21:37 PST 1993
  2.  
  3.  
  4. In article <C2M846.9FI@boi.hp.com> douglasg@gr.hp.com writes:
  5.  
  6.   > 
  7.   > I'm looking for an algorithm which determines if a point
  8.   > falls within an arbitrary (convex or concave) polygon.
  9.   > 
  10.   > Thanks,
  11.   > 
  12.   > Douglas Gennetten
  13.   > Hewlett-Packard
  14.   > 
  15.   > 
  16.   >
  17.  
  18. BOOLEAN PointInsideOfPolygon ( POLYGOON *P, VECTOR2D *p )
  19.   {
  20.   VECTOR2D o, v, w;
  21.   INDEX    ncross, N, n;
  22.  
  23.   ncros             = 0;
  24.   N                 = PolygonLength(P);   /* Number of vertices */
  25.   GivePolygonVertex ( P, N, &o );
  26.  
  27.   for ( n=1; n<=N; n++ )
  28.     {
  29.     GivePolygonVertex ( P, n, &v );
  30.  
  31.     if ( o.x >= p->x && v.x <  p->x ||
  32.      o.x <  p->x && v.x >= p->x  )
  33.       {
  34.       w.x = p->x;
  35.       LinearInterpolation ( &o, &v, &w );
  36.  
  37.       if ( w.x == p->x && w.y == p->y )
  38.     return(TRUE);
  39.       else if ( w.y > p->y )
  40.     ncross++;
  41.       }
  42.  
  43.     CopyVector2d ( &v, &o );
  44.     }
  45.  
  46.   if ( ncross%2 == 0 )
  47.     return(FALSE);
  48.   else
  49.     return(TRUE);
  50.   }
  51.  
  52. Cornelis Wessels
  53. kewe@bskewe.atr.bso.nl
  54.  
  55. Krommenoord 14
  56. 3079 ZT  ROTTERDAM
  57. The Netherlands
  58. +31 - 10 - 4826394
  59.